#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <stack>

const int MAXV = 100;
const int UNDISCOVER = 0;
const int DISCOVER = 1;
const int FINISHED = 2;

struct vertex
{
    int val;
    int weight;
    vertex* next;
};
struct graph
{
    vertex *vertexList[MAXV + 1];
    int degree[MAXV + 1]; 
    int vertexNum;
    int edgeNum;
    bool directed;
};

typedef graph* GraphPointer;

void printfGraph(graph *G);
void initGraph(graph *G);
void createGraph(graph *G, bool directed);
void insert_edge(graph *G, int v1, int v2, bool directed);
void BFS(graph *G);
void DFS(graph *G);

void initGraph(graph *G)
{
    int i;

    for ( i = 1; i < (MAXV+1); ++i)
    {
        G->vertexList[i] = NULL;
        G->degree[i] = 0;
    }
    G->edgeNum = 0;
    G->vertexNum = 0;
    G->directed = false;
}

void createGraph(graph *G, bool directed)
{
    
    int v1, v2;
    initGraph(G);
    scanf("%d",&(G->vertexNum));
    while(scanf("%d%d", &v1, &v2) != EOF)
    {
        insert_edge(G, v1, v2, directed);
    }
}

void insert_edge(graph *G, int v1, int v2, bool directed)
{
   vertex *p1, *p2;
   p1 = (vertex*)malloc(sizeof(vertex));
   p1->val = v2;
   p1->next = NULL;

   if (!G->vertexList[v1])
   {
       G->vertexList[v1] = p1; 
   }
   else
   {
       p2 = G->vertexList[v1];
       while(p2->next!=NULL) p2 = p2->next;
       p2->next = p1;
   }  
   G->degree[v1]++;
   if(directed == false)
        insert_edge(G, v2, v1, true);
   else
   {
        G->edgeNum++;
   }   
}

void printfGraph(graph *G)
{
    int i;
    vertex *p1;
    printf("%d\n", G->vertexNum);
    for (i = 1; i <= G->vertexNum; ++i)
    {
        printf("%d", i);
        p1 = G->vertexList[i];
        while(p1!= NULL)
        {
            printf("->%d", p1->val);
            p1 = p1->next;
        }
        printf("\n");
    }
}
void process_vertex_early(int v)
{

}
void process_edge(int vp, int vc)
{

}
void process_vertex_late(int v)
{

}
void BFS(graph *G, int start)
{
    int state[MAXV+1];
    int p[MAXV+1];
    int i = 0;
    int vp = 0, vc = 0;
    std::queue<int> q;
    vertex  *p1;
    
    //init state
    for (i = 1; i <= G->vertexNum; ++i)
    {   
        state[i] = UNDISCOVER;
        p[i] = 0;
    }

    q.push(start);
    state[start] = DISCOVER;
    printf("%d\n", start);
    while(!q.empty())
    {
        vp = q.front();
        q.pop();
        p1 = G->vertexList[vp];
        process_vertex_early(vp);
        while(p1 != NULL)
        {
            int vc = p1->val;
            if (state[vc] == UNDISCOVER)
            {
                printf(" %d", vc);
                p[vc] = vp;
                state[vc] = DISCOVER;
                q.push(vc); 
                process_edge(vp,vc);
            }
            p1 = p1->next;
        }
        process_vertex_late(vp);
        state[vp] = FINISHED;
        printf("\n");
    }

    for (i = 1; i <= G->vertexNum; ++i)
    {   
        printf("%d %d\n", state[i], p[i]);;
    }
}

int main(int argc, char const *argv[])
{
    graph G;
    createGraph(&G, false);
    printfGraph(&G);

    BFS(&G, 1);
    return 0;
}